\documentclass[
	article,
	12pt,
	oneside,
	a4paper,
	brazil]{article}

\pagenumbering{arabic}	% numeração nas páginas

%\setcitestyle{square}
%\setcounter{section}{0} %
%\setcounter{subsection}{0} %


% Pacotes fundamentais 
% ---
\usepackage{cmap}				% Mapear caracteres especiais no PDF
\usepackage{lmodern}			% Usa a fonte Latin Modern
\usepackage[T1]{fontenc}		% Selecao de codigos de fonte.
\usepackage[utf8]{inputenc}		% Codificacao do documento (conversão automática dos acentos)
\usepackage{indentfirst}		% Indenta o primeiro parágrafo de cada seção.
\usepackage{nomencl} 			% Lista de simbolos
\usepackage{color}				% Controle das cores
\usepackage{graphicx}			% Inclusão de gráficos
\usepackage[pdftex]{hyperref}	% Inclusao de links

\usepackage{float}		% forçar floable ficar [H]ere 
\usepackage{url}	
\usepackage[euler]{textgreek}	% letras gregas SEM begin{math} | instalar: texlive-textgreek
\usepackage[portuguese]{babel}	% Escrever "Tabela 1" ao invés de "Table 1"
%\usepackage{titling}

%\usepackage[margin=2.5cm]{geometry} % tamanho ocupado da folha

\newcommand{\OrientacaoDosProfs}[1]{
	%% Comente abaixo para tirar as orientacoes do PDF :)
%	\textcolor{blue}{ \footnotesize{Orientação: "\textsf{#1}"}}
}

\newcommand{\tamFigs}[0]{
	%% Ajuste para mudar a largura de todas as imagens:
	%\textwidth
	0.6\textwidth
}

%% Para: article
\renewcommand{\refname}{Referências}
%% Para: book, report
%\renewcommand{\bibname}{Referências}

\title{ACO aplicado à instâncias de TSP}
\author{Elenilson Pereira, Enrique Filiage, Felipe Müller, Lucas Padula}
\date{} %< omitindo data

\begin{document}	

\maketitle

\begin{normalsize}
	\begin{center}
	Introdução à inteligencia artificial 
	\linebreak \linebreak	
	Limeira, novembro de 2013
	\end{center}
\end{normalsize}

\section{Introdução}
\OrientacaoDosProfs{Deve conter informações gerais que justifiquem um trabalho nesse tema. O principal problema a ser resolvido e os objetivos do trabalho devem ser apresentados. A estrutura do restante do trabalho é também apresentada aqui.}

O Problema do Caixeiro Viajante 
(\textit{Travelling Salesman Problem} - TSP) 
é um problema de análise combinatória que alta complexidade, 
	% talvez falar de NP...
o que torna inviável de ser resolvido com uma busca exaustiva. Assim, o objetivo deste trabalho é aplicar a técnica bioinspirada da Otimização por Colônia de Formigas 
(\textit{Ant Colony Optimization} - ACO) 
para encontrar uma boa solução. 

O ACO puro será comparado com variações deste algoritmo,
	% que tipo de variação? 2-opt, 3-opt??
para aliar o impacto no desempenho final. Os casos de teste usados estão disponíveis na TSPLIB\footnote{Disponível em: \url{http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/} }.

\subsection{Bibliotecas disponíveis}
	Existem algumas bibliotecas disponíveis caso o desenvolvedor queira agilizar a implementação de determinado algoritmo ou heurística. Para a linguagem Java há a 
	\href{http://opt4j.sourceforge.net/}{Opt4J} 
	\cite{opt4jpaper}
	que é um \textit{framework} modular para otimizações de meta-heurísticas.
	



\section{Referencial teórico}
\OrientacaoDosProfs{Devem ser citados outros trabalhos (trabalhos correlatos) que também abordem o tema do trabalho. Os principais conceitos devem ser explicados aqui. Cada explicação deve conter uma citação.}

\subsection{Tamanho do melhor caminho}
	O tamanho do melhor caminho na TSPLIB não leva em consideração o retorno ao primeiro nó, mas este trabalho leva. Portanto, a tabela \ref{tabela:tamanhos} mostra qual é o menor percurso que somos capazes de encontrar:
	
	\begin{table}[htbp]
	\centering
	\begin{tabular}{|c|c|c|}
	\hline instância & tamanho original & com retorno ao nó inicial \\ 
	\hline eil76 & 538 & 545 \\ 
	\hline kroC100 & 20749 & 20750 \\ 
	\hline ch150 & 6528 & 6532 \\ 
	\hline 
	\end{tabular} 
	\caption{Diferença entre tamanhos}
	\label{tabela:tamanhos}
	\end{table}
	


\section{Metodologia}
\OrientacaoDosProfs{Devem ser apresentados todos os métodos utilizados. Por exemplo: Para agentes, a estrutura do agente e o algoritmo devem ser explicados aqui. Para Lógica Nebulosa, o modelo a ser utilizado (operadores, funções de pertinência etc) devem ser apresentados aqui.}

%TODO explicar por quê:
Todos os testes foram executados com 20 interações. Para os casos de teste foi usado 3 casos do TSPLIB, eil76, kroC100 e ch150. Com os melhores percursos (figs.: \ref{fig:eil76}, \ref{fig:kroC100} e 
\ref{fig:ch150}):

%\begin{figure}[!htb]
%     \centering
%     \includegraphics[width=\textwidth]{imgs/eil76.png} % [%scale=1]
%     \caption{Legenda da eil76}
%     \label{Label de referência para a eil76}
%\end{figure}
%
%\begin{figure}[!htb]
%     \centering
%     \includegraphics[width=\textwidth]{imgs/kroC100.png} % [%scale=1]
%     \caption{Legenda da kroC100}
%     \label{Label de referência para a kroC100}
%\end{figure}



\begin{figure}[htbp]
	\begin{minipage}[b]{0.45\linewidth}
		\centering
		\includegraphics[width=\tamFigs]{../ACO/src/img_ACO_puro/eil76_melhor_caminho.png}
		\caption{eil76}
		\label{fig:eil76}
	\end{minipage}
	\hspace{0.5cm}
	\begin{minipage}[b]{0.45\linewidth}
		\centering
		\includegraphics[width=\tamFigs]{../ACO/src/img_ACO_puro/kroC100_melhor_caminho.png}
		\caption{kroC100}
		\label{fig:kroC100}
	\end{minipage}
	\hspace{0.5cm}
	\begin{minipage}[b]{0.45\linewidth}
		\centering
		\includegraphics[width=\tamFigs]{../ACO/src/img_ACO_puro/ch150_melhor_caminho.png}
		\caption{ch150}
		\label{fig:ch150}
	\end{minipage}
\end{figure}

Foi testado vários valores para o fator de evaporação \textit{rho} (\begin{math}\rho\end{math}), 0,50 primeiros testes, 0,75 e 0,90.

\subsection{Operador 2-opt}
	O operador pode ser explicado como \cite{2opt_profAndre}:
	\begin{quote} \textit{
	elimine duas arestas da solução e insira novamente duas arestas de forma cruzada, ou seja,
	se as arestas removidas foram os pares que ligam as cidades (k1,k2) e (j1, j2), as arestas
	inseridas ligam as cidades na forma (k1,j2) e (j1,k2). Se esta nova configuração for melhor
	que a anterior, ou seja, se a distância diminuir, mantenha a nova rota. Caso contrário,
	escolha novamente duas arestas para análise.
	} \end{quote}	
%	Portanto, uma representação visual, é a fig. \ref{fig:2opt_visual}:
%	\begin{figure}[htbp]
%	\centering
%	\includegraphics[width=\tamFigs]{TSP_2OPT_digrafo-caso1.png}
%	\caption{}
%	\label{fig:2opt_visual}
%	\end{figure}

	Neste trabalho o 2-opt foi aplicado em 2 elementos escolhidos aleatoriamente, somente uma vez.
	Caso o caminho encurtasse, o caminho ficaria inalterado; caso contrário, voltaria a ser o percurso 
	original. Optou-se por não aplicar o 2-opt até encontrar uma melhoria no percurso porque, é muito
	difícil saber \textit{a priori} se a configuração atual pode ser melhorada. Ou seja, poderíamos 
	ficar continuamente tentando melhorar uma solução que não pode ser melhorada, desperdiçando 
	processamento. 

	Por fim, foi feito 24 execuções aplicando o 2-opt somente nos segmentos que se cruzavam, para o eil76.

\section{Resultados}
\OrientacaoDosProfs{Apresentação e discussão dos resultados. Não confunda metodologia com resultados. O resultado é a aplicação da metodologia. Por exemplo, para os agentes, as árvores de busca são resultados.}

\subsection{ACO puro}
	As figuras
	\ref{fig:eil76_melhoresCaminhosPorIteracao}, 
	\ref{fig:kroc100_melhoresCaminhosPorIteracao} e
	\ref{fig:ch150_melhoresCaminhosPorIteracao}
	mostram qual foi o comprimento do melhor caminho (eixo Y) ao longo das 20 iterações (eixo X), para
	todas as 20 execuções feitas (cada execução tem uma cor associada).
	\subsubsection{eil76}
		Após 20 execuções da instância eil76, o comprimento variou entre 572 e 589, obtendo uma média igual a 580,15, e desvio padrão igual à 4,59 
		(fig. \ref{fig:eil76_melhoresCaminhosPorIteracao}).
		\begin{figure}[htbp]
		\centering
		\includegraphics[width=\tamFigs]{../ACO/src/IteracoeseExecucoes_eil76_media.png}
		\caption{eil76 - Melhores caminhos de cada iteração (20 execuções)}
		\label{fig:eil76_melhoresCaminhosPorIteracao}
		\end{figure}
		
	\subsubsection{kroC100}
		O comprimento médio foi 22000,2, com desvio padrão de 188 
		(fig. \ref{fig:kroc100_melhoresCaminhosPorIteracao}).
		\begin{figure}[htbp]
		\centering
		\includegraphics[width=\tamFigs]{../ACO/src/IteracoeseExecucoes_kroC100_media.png}
		\caption{kroC100 - Melhores caminhos de cada iteração (20 execuções)}
		\label{fig:kroc100_melhoresCaminhosPorIteracao}
		\end{figure}
	
	\subsubsection{ch150}
		O comprimento médio foi 6884,4, com desvio padrão de 45,71
		(fig. \ref{fig:ch150_melhoresCaminhosPorIteracao}).
		\begin{figure}[htbp]
		\centering
		\includegraphics[width=\tamFigs]{../ACO/src/IteracoeseExecucoes_ch150_media.png}
		\caption{ch150 - Melhores caminhos de cada iteração (20 execuções)}
		\label{fig:ch150_melhoresCaminhosPorIteracao}
		\end{figure}

\subsection{Com operador 2-opt}
	Os gráficos \ref{fig:comOperador_eil76} e \ref{fig:comOperador_kroC100}
	mostram o desempenho do 2-opt, para eil76 e kroC100; não foi aplicado para ch150.
	\begin{figure}[htbp]
	\centering
	\includegraphics[width=\tamFigs]{../ACO/src/eil76_comparacao.png}
	\caption{eil76 - Com, e sem, formigas elitistas; e formiga elitista com 2-opt, para cada iteração (20 execuções)}
	\label{fig:comOperador_eil76}
	\end{figure}

	\begin{figure}[htbp]
	\centering
	\includegraphics[width=\tamFigs]{../ACO/src/kroC100_comparacao.png}
	\caption{kroC100 - Com e sem 2-opt para cada iteração (20 execuções)}
	\label{fig:comOperador_kroC100}
	\end{figure}

\subsection{Operador 2-opt somente em cruzamentos}
	Como pode ser visto nas figuras \ref{fig:eil76_melhoresCaminhosPorIteracao}, 
		\ref{fig:kroc100_melhoresCaminhosPorIteracao} e \ref{fig:ch150_melhoresCaminhosPorIteracao},
	os melhores caminhos 
	nenhum apresentam cruzamento, portanto, tentou-se aplicar o 2-opt diretamente nos cruzamentos do eil76.
	Desse modo,	foi obtido caminhos com comprimento entre 570 e 607; com média igual a 589,62 e 
	desvio padrão de 10,95.
	
	Mas, como pode ser observado na figura \ref{fig:eil76_desfazcruz_falho}
	o há um segmento (indicado por uma seta amarela) que cruza outros dois, nos pontos A e B 
	(respectivamente, verde e lilás).
	Isso demonstra que não é trivial aplicar o 2-opt em cruzamentos, afinal, não é possível saber qual
	das duas intersecções é melhor ser desfeita primeiro; ou, se ao desfazer algum cruzamento, um novo
	será criado.
	\begin{figure}[htbp]
	\centering
	\includegraphics[width=\tamFigs]{../ACO/src/img_2OPTcruz/v1_ACO_TSP_2OPT-qtdCid76-ex4-comp598-numIter20_day1_bom-exemplo.png}
	\caption{eil76 - qual dos cruzamentos deve ser desfeito primeiro?}
	\label{fig:eil76_desfazcruz_falho}
	\end{figure}

\subsection{Diferentes valores de \textit{rho} }
	Ao variar o valor de \textit{rho} com o eil76, obtivemos:
	
	\begin{table}[htbp]
	\centering
	\begin{tabular}{|c|c|c|c|}
	\hline valor de \textit{rho} & melhor caminho & média & desvio padrão \\ 
	\hline 0,50 & 572 & 580,15 & 4,59  \\ 
	\hline 0,75 & 570 & 577,76 & 3,98 \\ 
	\hline 0,90 & 570 & 576,53 & 6,45  \\ 
	\hline 
	\end{tabular} 
	\caption{eil76 - Ao variar \textit{rho} }
	\label{tabela:eil76_varios_rho}
	\end{table}	
\section{Conclusão}
	Para o eil76, não ter formigas elitistas causou uma pequena melhora (figura \ref{fig:comOperador_eil76}).
	Enquanto, para o kroC100 (fig. \ref{fig:comOperador_kroC100}), usar o 2-opt não mostrou vantagem, afinal, as médias dos comprimentos encontrados no final de cada execução, foi muito próximo.

	Ao fazer o feromônio evaporar com mais intensidade, 
	o comprimento médio do caminho encontrado diminuiu, pois, o algoritmo passa a buscar mais soluções antes de convergir, o que faz os resultados melhorarem, neste caso.
	
	Desfazer cruzamentos se mostrou algo mais complexo do que inicialmente parecia, afinal, não
	há uma forma de escolher qual cruzamento tem preferência para ser desfeito. Porque ao desfazer 
	qualquer um, pode-se introduzir novos que, por sua vez, ao serem desfeitos criarão outros; assim,
	hipoteticamente, criando um \textit{loop} de criação de cruzamentos.

\bibliographystyle{plain}	%< dava erro sem isso --'
\bibliography{referencias}

\end{document}
